package simple; /**
 * @projectName study-note
 * @package PACKAGE_NAME
 * @className PACKAGE_NAME.MaxSubArray
 */

/**
 * MaxSubArray
 * @description 最大子数组和
 * @author answer_wx
 * @date 2022/7/3 23:04
 * @version 1.0
 */
public class MaxSubArray {
    public static int maxSubArray(int[] nums) {
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        int pre = 0, max = nums[0];
        for (int num : nums) {
            pre = Math.max(num, pre + num);
            max = Math.max(pre, max);
        }
        return max;
    }

    // 1 1 2 3 5
    public static int fac(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }
        return fac(n - 1) + fac(n - 2);
    }

    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(maxSubArray(nums));
        System.out.println(fac(4));
    }
}